Algoritmo Q-learning como estratégia de exploração e/ou explotação para metaheurísticas GRASP e algoritmo genético

Techniques of optimization known as metaheuristics have achieved success in the resolution of many problems classified as NP-Hard. These methods use non deterministic approaches that reach very good solutions which, however, don t guarantee the determination of the global optimum. Beyond the inherent difficulties related to the complexity that characterizes the optimization problems, the metaheuristics still face the dilemma of xploration/exploitation, which consists of choosing between a greedy search and a wider exploration of the solution space. A way to guide such algorithms during the searching of better solutions is supplying them with more knowledge of the problem through the use of a intelligent agent, able to recognize promising regions and also identify when they should diversify the direction of the search. This way, this work proposes the use of Reinforcement Learning technique - Q-learning Algorithm - as exploration/exploitation strategy for the metaheuristics GRASP (Greedy Randomized Adaptive Search Procedure) and Genetic Algorithm. The GRASP metaheuristic uses Q-learning instead of the traditional greedy-random algorithm in the construction phase. This replacement has the purpose of improving the quality of the initial solutions that are used in the local search phase of the GRASP, and also provides for the metaheuristic an adaptive memory mechanism that allows the reuse of good previous decisions and also avoids the repetition of bad decisions. In the Genetic Algorithm, the Q-learning algorithm was used to generate an initial population of high fitness, and after a determined number of generations, where the rate of diversity of the population is less than a certain limit L, it also was applied to supply one of the parents to be used in the genetic crossover operator. Another significant change in the hybrid genetic algorithm is the proposal of a mutually interactive cooperation process between the genetic operators and the Q-learning algorithm. In this interactive/cooperative process, the Q-learning algorithm receives an additional update in the matrix of Q-values based on the current best solution of the Genetic Algorithm. The computational experiments presented in this thesis compares the results obtained with the implementation of traditional versions of GRASP metaheuristic and Genetic Algorithm, with those obtained using the proposed hybrid methods. Both algorithms had been applied successfully to the symmetrical Traveling Salesman Problem, which was modeled as a Markov decision process

Uma implementação paralela híbrida para o problema do caixeiro viajante usando algoritmos genéticos, GRASP e aprendizagem por reforço

The metaheuristics techiniques are known to solve optimization problems classified as NP-complete and are successful in obtaining good quality solutions. They use non-deterministic approaches to generate solutions that are close to the optimal, without the guarantee of finding the global optimum. Motivated by the difficulties in the resolution of these problems, this work proposes the development of parallel hybrid methods using the reinforcement learning, the metaheuristics GRASP and Genetic Algorithms. With the use of these techniques, we aim to contribute to improved efficiency in obtaining efficient solutions. In this case, instead of using the Q-learning algorithm by reinforcement learning, just as a technique for generating the initial solutions of metaheuristics, we use it in a cooperative and competitive approach with the Genetic Algorithm and GRASP, in an parallel implementation. In this context, was possible to verify that the implementations in this study showed satisfactory results, in both strategies, that is, in cooperation and competition between them and the cooperation and competition between groups. In some instances were found the global optimum, in others theses implementations reach close to it. In this sense was an analyze of the performance for this proposed approach was done and it shows a good performance on the requeriments that prove the efficiency and speedup (gain in speed with the parallel processing) of the implementations performed

Estudio y aplicación de metaheurísticas y comparación con métodos exhaustivos

Cuando nos enfrentamos a problemas reales haciendo uso de recursos computacionales, hemos de tener en cuenta que el número de posibles soluciones candidatas a tener en cuenta puede llegar a ser tan inmenso que abordarlas mediante técnicas algorítmicas clásicas, en la mayoría de los casos, pueden llegar a convertirse en un problema en sí mismo debido al gran coste en recursos que pueden llegar a generar. En este contexto, aspectos como el tiempo utilizado en la búsqueda de una solución mediante algoritmos de búsqueda exhaustiva tales como fuerza bruta, vuelta atrás, ramificación y poda, etc., puede llegar a ser prohibitivo en la práctica. Ante este problema que se nos plantea, podemos hacer un estudio sobre otros métodos, tales como los metaheurísticos, que, aunque no siempre aseguran la optimalidad de las soluciones producidas; tienen un tiempo de ejecución mucho menor que los métodos exhaustivos. En el presente trabajo hemos seleccionado dos problemas NP-completos de entre los más famosos de la literatura y hemos realizado un estudio de ambos. Concretamente, los problemas seleccionados han sido el TSP (Traveling Salesman Problem) y el problema de la Mochila 0-1. Por otro lado, hemos llevado a cabo un estudio sobre distintas metaheurísticas para poder resolver los problemas mencionados. Entre estas metaheurísticas, hemos seleccionado cuatro: metaheurísticas evolutivas, metaheurísticas inspiradas en colonias de hormigas, metaheurísticas simulated annealing (enfriamiento simulado) y metaheurísticas GRASP (Greedy Randomized Adaptive Search Procedure). Después de esto, cada problema ha sido resuelto aplicando tanto algoritmos de búsqueda exhaustiva como metaheurísticas. Una vez adaptados los algoritmos a la resolución de los problemas concretos, hemos realizado un estudio experimental, donde se realizaron comparativas de rendimiento. Finalmente, todo este trabajo ha sido plasmado en el desarrollo de una aplicación software, la cual consta de dos partes: una que contiene la implementación los algoritmos adaptados para la resolución de los problemas y que son ofrecidos a modo de servicios web y otra parte donde se ha implementado un cliente web que puede consumir estos servicios y realizar una presentación más vistosa de la ejecución de los algoritmos y los resultados obtenidos. Esta arquitectura podrá servir como base para futuras ampliaciones de este estudio.

O problema do caixeiro viajante alugador : um estudo algorítmico

The Car Rental Salesman Problem (CaRS) is a variant of the classical Traveling Salesman Problem which was not described in the literature where a tour of visits can be decomposed into contiguous paths that may be performed in different rental cars. The aim is to determine the Hamiltonian cycle that results in a final minimum cost, considering the cost of the route added to the cost of an expected penalty paid for each exchange of vehicles on the route. This penalty is due to the return of the car dropped to the base. This paper introduces the general problem and illustrates some examples, also featuring some of its associated variants. An overview of the complexity of this combinatorial problem is also outlined, to justify their classification in the NPhard class. A database of instances for the problem is presented, describing the methodology of its constitution. The presented problem is also the subject of a study based on experimental algorithmic implementation of six metaheuristic solutions, representing adaptations of the best of state-of-the-art heuristic programming. New neighborhoods, construction procedures, search operators, evolutionary agents, cooperation by multi-pheromone are created for this problem. Furtermore, computational experiments and comparative performance tests are conducted on a sample of 60 instances of the created database, aiming to offer a algorithm with an efficient solution for this problem. These results will illustrate the best performance reached by the transgenetic algorithm in all instances of the dataset

Aplicação do algoritmo de otimização por colônia de formigas sobre o problema do passeio do robô seletivo

This work seeks to propose and evaluate a change to the Ant Colony Optimization based on the results of experiments performed on the problem of Selective Ride Robot (PRS, a new problem, also proposed in this paper. Four metaheuristics are implemented, GRASP, VNS and two versions of Ant Colony Optimization, and their results are analyzed by running the algorithms over 32 instances created during this work. The metaheuristics also have their results compared to an exact approach. The results show that the algorithm implemented using the GRASP metaheuristic show good results. The version of the multicolony ant colony algorithm, proposed and evaluated in this work, shows the best results

O problema do caixeiro alugador com coleta de bonus: um estudo algoritmico

This paper introduces a new variant of the Traveling Car Renter Problem, named Prizecollecting Traveling Car Renter Problem. In this problem, a set of vertices, each associated with a bonus, and a set of vehicles are given. The objective is to determine a cycle that visits some vertices collecting, at least, a pre-defined bonus, and minimizing the cost of the tour that can be traveled with different vehicles. A mathematical formulation is presented and implemented in a solver to produce results for sixty-two instances. The proposed problem is also subject of an experimental study based on the algorithmic application of four metaheuristics representing the best adaptations of the state of the art of the heuristic programming.We also provide new local search operators which exploit the neighborhoods of the problem, construction procedures and adjustments, created specifically for the addressed problem. Comparative computational experiments and performance tests are performed on a sample of 80 instances, aiming to offer a competitive algorithm to the problem. We conclude that memetic algorithms, computational transgenetic and a hybrid evolutive algorithm are competitive in tests performed

Análisis de la eficiencia de los sistemas de colonias de hormigas para problemas de accesibilidad

A pesar de los avances en materia de predicción, los desastres naturales siguen teniendo consecuencias devastadoras. Entre los principales problemas a los que se enfrentan los equipos de ayuda y rescate después de un desastre natural o provocado por el hombre se encuentra la planificación de las tareas de reparación de carreteras para conseguir la máxima ventaja de los limitados recursos económicos y humanos. En la presente Tesis Fin de Máster se intenta dar solución al problema de la accesibilidad, es decir, maximizar el número de supervivientes que consiguen alcanzar el centro regional más cercano en un tiempo mínimo mediante la planificación de qué carreteras rurales deberían ser reparadas dados unos recursos económicos y humanos limitados. Como se puede observar, es un problema combinatorio ya que el número de planes de reparación y conexiones entre las ciudades y los centros regionales crece de forma exponencial con el tamaño del problema. Para la resolución del problema se comienza analizando una adaptación básica de los sistemas de colonias de hormigas propuesta por otro autor y se proponen múltiples mejoras sobre la misma. Posteriormente, se propone una nueva adaptación más avanzada de los sistemas de colonias de hormiga al problema, el ACS con doble hormiga. Este sistema hace uso de dos tipos distintos de hormigas, la exploradora y la trabajadora, para resolver simultáneamente el problema de encontrar los caminos más rápidos desde cada ciudad a su centro regional más cercano (exploradora), y el de obtener el plan óptimo de reparación que maximice la accesibilidad de la red (trabajadora). El algoritmo propuesto se ilustra por medio de un ejemplo de gran tamaño que simula el desastre natural ocurrido en Haití, y su rendimiento es comparado con la combinación de dos metaheurísticas, GRASP y VNS.---ABSTRACT---In spite of the advances in forecasting, natural disaster continue to ocasionate devastating consequences. One of the main problems relief teams face after a natural or man-made disaster is how to plan rural road repair work to take maximum advantage of the limited available financial and human resources. In this Master´s Final Project we account for the accesability issue, that is, to maximize the number of survivors that reach the nearest regional center in a minimum time by planning whic rural roads should be repaired given the limited financial and human resources. This is a combinatorial problem since the number of possible repairing solutions and connections between cities and regional centers grows exponentially with the size of the problem. In order to solve the problem, we analyze the basic ant colony system adaptation proposed by another author and point out multiple improvements on it. Then, we propose a novel and more advance adaptation of the ant colony systems to the problem, the double- ant ACS. This system makes use of two diferent type of ants, the explorer and the worker, to simultaneously solve the problem of finding the shorthest paths from each city to their nearest regional center (explorer), and the problem of identifying the optimal repairing plan that maximize the network accesability (worker). The proposed algorithm is illustrated by means of a big size example that simulates the natural disaster occurred in Haiti, and its performance is compared with a combination of two metaheuristics, GRASP and VNS.

Reconfiguração de alimentadores em sistemas de distribuição usando a metaheurística GRASP

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Aplicação de técnicas metaheurísticas para resolver o problema de coordenação de carregamento de veículos elétricos em sistemas de distribuição

Pós-graduação em Engenharia Elétrica - FEIS

Touch, grasp, deliver and control : functional cross-talk between microtubules and cell adhesions

Cross-talk between microtubule networks and sites of cell-matrix and cell-cell adhesion has profound impact on these structures and is essential for proper cell organization, polarization and motility. Components of adhesion sites can interact directly with microtubules or with proteins that specifically associate with microtubule plus ends and minus ends and in this way capture, stabilize or destabilize microtubules. In their turn, microtubules can serve as routes for delivery of structural and regulatory factors that control adhesion site turnover. In addition, the microtubule lattice or growing microtubule plus ends can serve as diffusional sinks that accumulate and scaffold regulatory molecules, thereby affecting their activity in the vicinity of adhesions. Combination of these mechanisms underlies the functional co-operation between microtubules and adhesion sites and defines their dynamic behavior.

Multiple grasp-specific representations of tool dynamics mediate skillful manipulation.

Skillful tool use requires knowledge of the dynamic properties of tools in order to specify the mapping between applied force and tool motion. Importantly, this mapping depends on the orientation of the tool in the hand. Here we investigate the representation of dynamics during skillful manipulation of a tool that can be grasped at different orientations. We ask whether the motor system uses a single general representation of dynamics for all grasp contexts or whether it uses multiple grasp-specific representations. Using a novel robotic interface, subjects rotated a virtual tool whose orientation relative to the hand could be varied. Subjects could immediately anticipate the force direction for each orientation of the tool based on its visual geometry, and, with experience, they learned to parameterize the force magnitude. Surprisingly, this parameterization of force magnitude showed limited generalization when the orientation of the tool changed. Had subjects parameterized a single general representation, full generalization would be expected. Thus, our results suggest that object dynamics are captured by multiple representations, each of which encodes the mapping associated with a specific grasp context. We suggest that the concept of grasp-specific representations may provide a unifying framework for interpreting previous results related to dynamics learning.

Utilização do software GRASP para gerar arquivo de coordenadas com valores de potencial eletrostático.

Com o intuito de disponibilizar um banco de dados de valores de potencial eletrostático para todas as estruturas de proteínas depositadas no PDB, foi utilizado o programa GRASP (Graphical Representation and Analysis of Structural Properties) (Nicholls et al., 1991) para geração deste banco de dados.